#!/usr/bin/env python
# encoding: utf-8
'''
@author: Excelsiorly
@license: (C) Copyright 2021, All Rights Reserved.
@contact: excelsiorly@qq.com
@file: 0019.py
@time: 2021/9/15 14:04
@desc:
'''


class Solution:
    def maxValue(self, grid: List[List[int]]) -> int:
        dp = [[0 for j in range(len(grid[i]))] for i in range(len(grid))]
        m, n = len(grid), len(grid[0])  # 行数、列数
        dp[0][0] = grid[0][0]
        # 初始化第一行
        for i in range(1, n):
            dp[0][i] = dp[0][i - 1] + grid[0][i]
        # 初始化第一列
        for j in range(1, m):
            dp[j][0] = dp[0][j - 1] + grid[j][0]

        for i in range(1, m):
            for j in range(1, n):
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]

        return dp[-1][-1]

if __name__ == '__main__':
    sl = Solution()
    inp = [[7,2],[6,6],[8,6],[8,7],[5,0],[6,0]]
    res = sl.maxValue(inp)
    print(res)